class Solution1 {
    boolean[][] vis;
    int n,m;
    int count = 0;
    int[] xx = {1,-1,0,0};
    int[] yy = {0,0,1,-1};
    int cnt = 0;
    public int uniquePathsIII(int[][] grid) {
        n = grid.length;
        m = grid[0].length;
        vis = new boolean[n][m];
        int x = 0, y = 0;
        for(int i = 0;i<n; i++) {
            for(int j = 0;j <m; j++) {
                if(grid[i][j] == 1) {
                    x = i;
                    y = j;
                }
                if(grid[i][j] == 0) {
                    cnt++;
                }
            }
        }
        vis[x][y]= true;
        System.out.println(cnt);
        dfs(grid,x,y);
        return count;
    }
    public void dfs(int[][] grid, int x, int y) {
        if(grid[x][y] == 2 && cnt == -1) {
            count++;
            return;
        }
        for(int i = 0;i <4; i++) {
            int dx = x+xx[i];
            int dy = y+yy[i];
            if(dx>=0 && dx<n && dy>=0 && dy<m && grid[dx][dy]!=-1 && !vis[dx][dy]) {
                vis[dx][dy] = true;
                cnt--;
                dfs(grid,dx,dy);
                vis[dx][dy] = false;
                cnt++;
            }
        }
    }
}


class Solution {
    int n,m;
    int[] xx = {1,-1,0,0};
    int[] yy = {0,0,1,-1};
    boolean[][] vis;
    int st = 0;
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        n = image.length;
        m = image[0].length;
        System.out.println(n + " " + m);
        st = image[sr][sc];
        vis = new boolean[n][m];
        image[sr][sc]= color;
        vis[sr][sc] = true;
        dfs(image,sr,sc,color);
        return image;
    }
    public void dfs(int[][] image, int x, int y, int color){
        for(int i =0; i<4; i++) {
            int dx = x + xx[i];
            int dy = y + yy[i];
            if(dx>=0 && dx<n && dy >= 0 && dy <m && image[dx][dy] == st && !vis[dx][dy]) {
                System.out.println(dx + " " + dy);
                vis[dx][dy] = true;
                image[dx][dy] = color;
                dfs(image, dx,dy,color);
            }
        }
    }
}

public class Test {
    public static void main(String[] args) {
        int[][] image = {{0,0,0},{0,0,0}};
        int[][] ret = new Solution().floodFill(image,1,1,2);
        for(int i =0; i<2; i++) {
            for(int j = 0; j<3; j++) {
                System.out.print(ret[i][j] + " ");
            }
            System.out.println();
        }
    }
    public static void main1(String[] args) {
        int[][] grid = {{0,1},{2,0}};
        int ret = new Solution1().uniquePathsIII(grid);
    }
}
